# 给定一个经过编码的字符串，返回它解码后的字符串。 
# 
#  编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 
# 
#  你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。 
# 
#  此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：s = "3[a]2[bc]"
# 输出："aaabcbc"
#  
# 
#  示例 2： 
# 
#  
# 输入：s = "3[a2[c]]"
# 输出："accaccacc"
#  
# 
#  示例 3： 
# 
#  
# 输入：s = "2[abc]3[cd]ef"
# 输出："abcabccdcdcdef"
#  
# 
#  示例 4： 
# 
#  
# 输入：s = "abc3[cd]xyz"
# 输出："abccdcdcdxyz"
#  
# 
#  
# 
#  提示： 
# 
#  
#  1 <= s.length <= 30 
#  
#  s 由小写英文字母、数字和方括号
#  
# 
#  Related Topics 栈 递归 字符串 👍 1908 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def decodeString(self, s: str) -> str:
        """
        方法1:使用递归深度遍历
        :param s:
        :return:

        def dfs(s1: str):
            i, n, num = 0, len(s1), 0
            res = ''
            while i < n:
                c = s1[i]
                if c.isdigit():
                    while s1[i].isdigit() and i < n:
                        num = num * 10 + int(s1[i])
                        i += 1
                    # 多加了一个1,需要减去
                    i -= 1
                elif c == '[':
                    temp = 0
                    for j in range(i, n):
                        if s1[j] == '[':
                            temp -= 1
                        elif s1[j] == ']':
                            temp += 1
                        if temp == 0:
                            # 截取字符串递归
                            subres = dfs(s1[i + 1:j])
                            res += num * subres
                            # 注意用过一次num后要把num清0留到下次用
                            num = 0
                            i = j
                            break

                elif c.isalpha():
                    res += c
                i += 1
            return res

        return dfs(s)
        """
        """
            方法2:使用栈来实现
            :param s: 
            :return: 
        """
        stack = []
        i, n, num = 0, len(s), 0
        cur_str = ''
        while i < n:
            c = s[i]
            if c.isdigit():
                num = num * 10 + int(s[i])

            elif c == '[':
                # cur_str和num一起入栈
                stack.append((cur_str, num))
                # cur_str,num复位
                num = 0
                cur_str = ''
            elif c == ']':
                pre_str, num = stack.pop()
                cur_str = pre_str + (num * cur_str)
                num = 0
            else:
                cur_str += c

            i += 1
        return cur_str


# leetcode submit region end(Prohibit modification and deletion)

print(Solution().decodeString(s="3[a]2[bc]"))
